class code5 {
    //电话号码的字母组合
    List<String> ret;
    StringBuffer path;
    String[] hash = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    public List<String> letterCombinations(String digits) {
        ret = new ArrayList<>();
        path = new StringBuffer();

        if(digits.length()==0) return ret;
        dfs(digits,0);

        return ret;
    }
    public void dfs(String digits,int pos) {
        if(path.length()==digits.length()) {
            ret.add(path.toString());
            return;
        }

        String cur = hash[digits.charAt(pos)-'0'-2];
        for(int i=0;i<cur.length();i++) {
            path.append(cur.charAt(i));
            dfs(digits,pos+1);
            path.deleteCharAt(path.length()-1);//回溯
        }

    }
}